1. Field of the Invention
The invention relates to the field of computer systems. More specifically, the invention relates to software for performing multiplication operations.
2. Background Information
Since numerous routines executed on processors require multiplication, processors typically are capable of executing an instruction to multiply together one or more operands. Unfortunately, certain routines require a higher-precision multiply (e.g., a 16 bit by 32 bit multiply) than is supported by the multiply instruction(s) of a processor. When no single multiply instruction can perform the higher-precision multiply, different combinations of instructions must be used.
Binary numbers are typically used either to represent unsigned numbers or signed numbers using 2's complement signed representation. The multiplication operation is performed in a different fashion for signed and unsigned numbers.
The full result of a N bit by N bit multiplication requires 2*N bits to represent. A `full-multiply` instruction is one which multiplies two N bit numbers and yields the full 2*N bit result. Processors that lack such a multiply instruction use two instructions: 1) a `multiply-high` instruction which produces the upper N bits of the result; and 2) a `multiply-low` instruction which produces the lower N bits. Additional instructions are used to combine the two halves if necessary.
The full result of a 2*N bit by N bit multiplication requires 3*N bits to represent, however in many cases not all the bits of the result are needed. A smaller range out of the 3*N bit result is often used, most typically 2*N bits. If the multiplicands and result represent integers, the lower 2*N bits will be used (in this case an error may occur if the result does not fall into the range which can be represented by 2*N bits). If the multiplicands and/or result represent fixed-point numbers, some other range of 2*N bits out of the 3*N bit result will be used, depending on the radix point locations. Table 1 illustrates the selection of 2*N bits out of a 3*N bit result. In Table 1, `K` and `N-K` respectively represent the number of unused upper and lower bits, while the 2*N bits from the N-K+1 bit to the 3*N-K bit are used. K may range from 0 to N.
TABLE 1 ______________________________________ 3*N Bit Result ______________________________________ K Bits 2*N Bits Used N-K Bits ______________________________________
FIG. 1 is a data flow diagram illustrating a method of using two N bit by N bit multiply operations to perform an N bit by 2*N bit unsigned multiplication. Although the complete result of such a multiplication is 3*N bits long, typically only part of the 3*N bit result is used in further computations (e.g., 2*N bits are used out of the full 3*N bit result as illustrated in Table 1). In FIG. 1, rectangles are used to illustrate data and ovals are used to illustrate operations. FIG. 1 shows a value A represented in 2*N bits and a value B represented in N bits. The value A is divided into a most significant half (A.sub.HIGH) and a least significant half (A.sub.LOW).
In step 110, A.sub.HIGH is multiplied by B using unsigned multiplication to generate B*A.sub.HIGH. In step 120, A.sub.LOW is multiplied by B using unsigned multiplication to generate B*A.sub.LOW. Note that both steps 110 and 120 perform a full N bit multiplication which multiplies two N bit numbers to produce a 2*N bit result. On processors which do not have a full multiply but have multiply-high and multiply-low instructions, steps 110 and 120 will be performed by either: 1) using multiple instructions; or 2) using multiply-high/low instructions that perform 2*N bit by 2*N bit multiplications.
Aligning the least significant bit position of B*A.sub.HIGH with the (N+1) least significant bit position of B*A.sub.LOW and then performing an addition operation yields B*A. The shifting in steps 130 and 140 illustrate one way of properly aligning the values for the addition operation (step 150) that generates a value representing B*A. In step 130, B*A.sub.HIGH is logically shifted left K bits to generate K&lt;&lt;(B*A.sub.HIGH). While in step 140, the B*A.sub.LOW is arithmetically shifted right (N-K) bits to generate (B*A.sub.LOW)&gt;&gt;(N-K). It is worthwhile to note that the shifting of B*A.sub.LOW to the right allows for the use of a 2*N bit addition.
While FIG. 1 illustrates a method for performing unsigned multiplications, often times signed multiplications are required. However, the method of FIG. 1 cannot be used to perform signed multiplications.